package leetcode.design;

import java.util.*;

class MajorityChecker {

    private final int[] nums;
    // key为元素，value为元素出现在nums数组中的索引下标集合
    private final Map<Integer, List<Integer>> map = new HashMap<>();

    public MajorityChecker(int[] arr) {
        this.nums = arr;
        // 初始化时计算元素与出现下标的映射关系
        for (int i = 0; i < nums.length; i++) {
            List<Integer> posList = map.get(nums[i]);
            if (posList == null) {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                map.put(nums[i], list);
            } else {
                posList.add(i);
            }
        }
    }

    public int query(int left, int right, int threshold) {
        int k = 20;
        // 循环随机二十次尝试，如果都找不到绝对众数，则认为子数组不存在绝对众数
        for (int i = 0; i < k; i++) {
            Random random = new Random();
            int index = random.nextInt(right - left + 1) + left;
            int x = nums[index];
            List<Integer> posList = map.get(x);
            int count = getShowCount(posList, left, right);
            if (count >= (right - left + 1) / 2) {
                if (count >= threshold) {
                    return x;
                } else {
                    return -1;
                }
            }
        }
        return -1;
    }

    /**
     * 获取子数组中选取的随机元素出现的次数
     *
     * @param posList
     * @param left
     * @param right
     * @return
     */
    private int getShowCount(List<Integer> posList, int left, int right) {
        // 左边界无所谓
        int firstPos = binarySearch(posList, left);
        // 需要校正右边界
        int lastPos = binarySearch(posList, right);
        // 如果搜索右边界找不到，则需要回补-1
        if (lastPos > posList.size() - 1 || posList.get(lastPos) > right) {
            lastPos--;
        }
        return lastPos - firstPos + 1;
    }

    /**
     * @param posList 没有重复的下标元素，并且下标位置递增
     * @param key
     * @return
     */
    private int binarySearch(List<Integer> posList, int key) {
        if (posList.isEmpty()) {
            return -1;
        }
        int left = 0;
        int right = posList.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            Integer num = posList.get(mid);
            if (num == key) {
                return mid;
            } else if (num < key) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // 找不到时，返回第一个大于key的元素索引（有可能越界出现right == posList.size()）
        return left;
    }
}

/**
 * Your MajorityChecker object will be instantiated and called as such:
 * MajorityChecker obj = new MajorityChecker(arr);
 * int param_1 = obj.query(left,right,threshold);
 */
public class leetcode1157 {
    public static void main(String[] args) {
//        test1157_1();
        test1157_2();
    }

    private static void test1157_2() {
        int[] nums = {2, 2, 1, 2, 1, 2, 2, 1, 1, 2};
        MajorityChecker majorityChecker = new MajorityChecker(nums);
        // -1,-1,2,-1,2,2,-1,-1,-1,2
        System.out.println(majorityChecker.query(2, 5, 4));
        System.out.println(majorityChecker.query(0, 5, 6));
        System.out.println(majorityChecker.query(0, 1, 2));
        System.out.println(majorityChecker.query(2, 3, 2));
        System.out.println(majorityChecker.query(6, 6, 1));
        System.out.println(majorityChecker.query(0, 3, 3));
        System.out.println(majorityChecker.query(4, 9, 6));
        System.out.println(majorityChecker.query(4, 8, 4));
        System.out.println(majorityChecker.query(5, 9, 5));
        System.out.println(majorityChecker.query(0, 1, 2));
    }

    private static void test1157_1() {
        int[] nums = {1, 1, 2, 2, 1, 1};
        MajorityChecker majorityChecker = new MajorityChecker(nums);
        System.out.println(majorityChecker.query(0, 5, 4)); // 返回 1
        System.out.println(majorityChecker.query(0, 3, 3)); // 返回 -1
        System.out.println(majorityChecker.query(2, 3, 2)); // 返回 2
    }
}
